package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.List;

/**
 * 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
 *
 * <p>如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
 *
 * <p>而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1104 {

  public List<Integer> pathInZigZagTree(int label) {
    int level = 1;
    while (end(level) < label) level++;
    int[] r = new int[level];
    int idx = level - 1, cur = label;
    while (idx >= 0) {
      r[idx--] = cur;
      int tot = (int) Math.pow(2, level - 1);
      int start = start(level), end = end(level);
      if (level % 2 == 0) { // 偶数层从右边到左边递增
        int j = tot / 2;
        for (int i = start; i <= end; i += 2, j--) { // i递增 向左边移动，说明上面一层就离左边越来越近，j就越小
          if (cur == i || (i + 1) == cur) break; // 两个节点
        }
        int pre = start(level - 1); // 奇数层从左到右递增
        while (j-- > 1) pre++;
        cur = pre;
      } else {
        int j = 1;
        for (int i = start; i <= end; i += 2, j++) {
          if (cur == i || cur == (i + 1)) break;
        }
        int pre = end(level - 1);
        while (j-- > 1) pre--;
        cur = pre;
      }
      level--;
    }
    List<Integer> list = new ArrayList<>();
    for (int i : r) {
      list.add(i);
    }
    return list;
  }

  public int start(int level) {
    return (int) Math.pow(2, level - 1);
  }

  public int end(int level) {
    int a = start(level);
    return a + a - 1;
  }
}

class Demo1140 {
  public static void main(String[] args) {
    Test1104 t = new Test1104();
    List<Integer> list = t.pathInZigZagTree(14);
    list.forEach(System.out::println);
  }
}
